package main.leetcode.clockin.March;

/**
 * 365.水壶问题
 *
 * <p>有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
 *
 * <p>如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
 *
 * <p>你允许：装满任意一个水壶；清空任意一个水壶；从一个水壶向另外一个水壶倒水，直到装满或者倒空
 *
 * <p>示例 1: (From the famous "Die Hard" example)输入: x = 3, y = 5, z = 4 输出: True
 *
 * <p>示例 2:输入: x = 2, y = 6, z = 5 输出: False
 */
public class day21 {
    public static void main(String[] args) {
        System.out.println(new day21().canMeasureWater(2, 6, 5));
    }

    /* bfs */
    //    public boolean canMeasureWater(int x, int y, int z) {
    //        if (z == 0) return true;
    //        if (x + y < z) return false;
    //
    //        Queue<State> queue = new LinkedList<>(); // 存储状态
    //        Set<State> isVisited = new HashSet<>(); // 存储已尝试过的状态
    //
    //        // 初始化
    //        State init = new State(0, 0);
    //        queue.add(init);
    //        isVisited.add(init);
    //
    //        State head;
    //        int currX, currY;
    //        while (!queue.isEmpty()) {
    //            head = queue.poll();
    //            currX = head.getX();
    //            currY = head.getY();
    //
    //            // 可以的几种状态
    //            if (z == currX || z == currY || z == currX + currY) return true;
    //
    //            // 从当前状态获得可能的下一步状态
    //            List<State> nextState = getNextState(currX, currY, x, y);
    //            // 把没碰到过的状态加入队列
    //            for (State state : nextState) {
    //                if (!isVisited.contains(state)) {
    //                    queue.add(state);
    //                    isVisited.add(state);
    //                }
    //            }
    //        }
    //        return false;
    //    }
    //
    //    // 从总共的8种状态中获取可能会出现的状态
    //    private List<State> getNextState(int currX, int currY, int x, int y) {
    //        List<State> list = new ArrayList<>(8);
    //
    //            /* 外部装满 */
    //            State state1 = new State(x, currY); // X
    //            State state2 = new State(currX, y); // Y
    //
    //            /* 往外清空 */
    //            State state3 = new State(0, currY); // X
    //            State state4 = new State(currX, 0); // Y
    //
    //            /* 倒水（两种结果，装满了另一桶，或者，装不满另一桶 */
    //            // X倒向Y
    //            State state5 = new State(currX - (y - currY), y); // 装满Y，X少了
    //            State state6 = new State(0, currY + currX); // 装不满Y，X空了
    //            // Y倒向X
    //            State state7 = new State(x, currY - (x - currX)); // 装满X，Y少了
    //            State state8 = new State(currX + currY, 0); // 装不满X，Y空了
    //
    //            list.add(state1);
    //            list.add(state2);
    //            list.add(state3);
    //            list.add(state4);
    //
    //            if (currX - (y - currY) >= 0) list.add(state5);
    //            if (currX + currY <= y) list.add(state6);
    //            if (currY - (x - currX) >= 0) list.add(state7);
    //            if (currX + currY <= x) list.add(state8);
    //
    //        return list;
    //    }
    //
    //    // 自定义状态类，存储当前状态（X，Y)
    //    private class State {
    //        int X;
    //        int Y;
    //
    //        State(int x, int y) {
    //            X = x;
    //            Y = y;
    //        }
    //
    //        int getY() {
    //            return Y;
    //        }
    //
    //        public int getX() {
    //            return X;
    //        }
    //
    //        @Override
    //        public boolean equals(Object obj) {
    //            if (obj == this) return true;
    //            if (!(obj instanceof State)) return false;
    //            State state = (State) obj;
    //            return Objects.equals(state.X, X) && Objects.equals(state.Y, Y);
    //        }
    //
    //        @Override
    //        public int hashCode() {
    //            return Objects.hash(X, Y);
    //        }
    //    }

    /* bfs 优化 */
    //    public boolean canMeasureWater(int x, int y, int z) {
    //        if (z == 0) return true;
    //        if (x + y < z) return false;
    //
    //        Set<Integer> isVisited = new HashSet<>();
    //        Queue<Integer> queue = new LinkedList<>();
    //        queue.add(0);
    //
    //        // 之前的思路都是以X，Y为状态量来看，这里直接以总水量来看，所以少了个互相倒水的复杂讨论
    //        // 每次改变总水量只能是X或Y升的增加，或者是X或Y升的减少，就算是相互倒水其实也是可以转化为
    //        while (!queue.isEmpty()) {
    //            int curr = queue.poll(); // 当前总水量
    //            if (curr + x <= x + y && isVisited.add(curr + x)) queue.add(curr + x); // 装满X
    //            if (curr + y <= x + y && isVisited.add(curr + y)) queue.add(curr + y); // 装满Y
    //            if (curr - x >= 0 && isVisited.add(curr - x)) queue.add(curr - x); // 清空X
    //            if (curr - y >= 0 && isVisited.add(curr - y)) queue.add(curr - y); // 清空Y
    //            if (isVisited.contains(z)) return true; // 达到水量
    //        }
    //        return false;
    //    }

    // 数学思路（贝祖定理）
    public boolean canMeasureWater(int x, int y, int z) {
        if (z == 0) return true;
        if (x + y < z) return false;

        // 由上种方式想到了数学思路，有ax+by=z。即，只要找到满足要求的a，b那么就可以实现倒水
        // 贝祖定理告诉我们，ax+by=zax+by=z 有解当且仅当 z 是 x, y 的最大公约数的倍数
        // 因此我们只需要找到 x, y 的最大公约数并判断 z 是否是它的倍数即可
        return z % gcd(x, y) == 0;
    }

    private int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}
